package leetcode_2501_2600;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_2537 {
    public static void main(String[] args) {
        System.out.println(countGood(new int[]{1, 1, 1, 1, 1}, 10));
        System.out.println(countGood(new int[]{3,1,4,3,2,2,4}, 2));
    }
    private static long countGood(int[] nums, int k) {
        int n = nums.length, l = 0, r = l;
        Map<Integer, Integer> map = new HashMap<>();
        long ans = 0;
        int count = 0;
        while (l < n){
            if (r >= n)
                break;
            int num = nums[r];
            if (map.containsKey(num)){
                int pre = map.get(num);
                count += pre;
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1);
            }
            while (count >= k){
                ans += n - r;
                if (map.get(nums[l]) > 1){
                    Integer pre = map.get(nums[l]);
                    count -= pre - 1;
                    map.put(nums[l], pre - 1);
                }else {
                    map.remove(nums[l]);
                }
                l++;
            }
            r++;
        }
        return ans;
    }
}
